import java.util.HashMap;
import java.util.Map;

/**
 * 146. LRU 缓存
 * https://leetcode.cn/problems/lru-cache/description/?envType=study-plan-v2&envId=top-100-liked
 */
class LRUCache {
    int capacity;
    Map<Integer, DLinkedNode> map;
    DLinkedNode head;
    DLinkedNode tail;

    public LRUCache(int capacity) {
        this.capacity = capacity;
        map = new HashMap<>();
        head = new DLinkedNode(-1, -1);
        tail = new DLinkedNode(-1, -1);

        // 处理这个头结点和尾节点
        head.next = tail;
        tail.prev = head;
    }

    public int get(int key) {
        // 1、先在hash表查询有没有这个 key
        if (!map.containsKey(key)) {
            return -1;
        }

        // 代码执行到这，说明hash表里有这个key
        // 2、先拿到这个key 的 value
        int ret = map.get(key).value;

        // 3、拿到后还要更新链表，这个是最近操作过的key，所以要尾插，放进尾部
        // 要拿到这个链表的节点，把它进行尾差
        DLinkedNode tmp = map.get(key);
        addTail(tmp);// 尾插

        // 4、返回 这个key 对应的 value
        return ret;
    }

    public void put(int key, int value) {
        // 1、判断 map 里有没有这个key-value
        if(map.containsKey(key)) {
            // 有
            // 就要更新 value 值
            map.get(key).value = value;
            addTail(map.get(key));
            map.put(key, map.get(key));
        } else {
            // 没有
            // 1、先直接放进去，同时链表要尾差进去，表示最近使用过这个key
            DLinkedNode tmp = new DLinkedNode(key, value);
            addTail(tmp); // 尾插
            map.put(key, tmp);


            // 2、判断容量超了没，超了就要删除链表的头结点，对应的map也要删除
            if(map.size() > capacity) {
                // 超了
                // 删除对应的map
                map.remove(head.next.key);
                // 删除链表头结点
                removeHead();
            }
        }
    }

    // 尾插
    public void addTail(DLinkedNode node) {
        DLinkedNode prev;
        DLinkedNode next;

        // 删除当前 node 节点位置(要尾插的节点就是链表中的元素)
        if(node.next != tail && node.prev != null && node.next != null) {
            // 这个是提取出原本链表中的节点，因为get拿了这个节点，说明这个节点是最近使用过的，要进行尾插
            prev = node.prev;
            next = node.next;
            // 连接删除当前节点后的前后两个节点
            prev.next = next;
            next.prev = prev;
            node.prev = null;
            node.next = null;

        } else if(node.prev != null && node.next != null) {
            // 说明这个就是尾节点，那就不用进行尾插了
            return;
        }

        // 尾插
        prev = tail.prev;
        prev.next = node;
        node.next = tail;
        node.prev = prev;
        tail.prev = node;
    }

    // 头删
    public void removeHead() {
        DLinkedNode cur = head.next;
        DLinkedNode next = cur.next;
        head.next = next;
        next.prev = head;
        cur.prev = null;
        cur.next = null;
    }


    class DLinkedNode {
        int key;
        int value;

        DLinkedNode prev;
        DLinkedNode next;

        public DLinkedNode() {}
        public DLinkedNode(int key, int value) {this.key = key; this.value = value;}
    }
}